package cn.kuick.match2.test1;

import java.util.ArrayList;
import java.util.Stack;

public class SquareNumber {
	public static boolean isMatch(Stack<Integer> sb, int target) {
		int sum = 0;
		
		for(int i=0; i<sb.size(); i++) {
			sum += sb.get(i).intValue();
		}
		
		return sum == target;
	}
	
	public static boolean isOk(ArrayList<Integer[]> output, Stack<Integer> sb, int target) {
		
		int min = findMin(output);
		
		if (sb.size() <= min) {
			int sum = 0;
			
			for(int i=0; i<sb.size(); i++) {
				sum += sb.get(i).intValue();
			}
			
			return sum < target;
		}
		
		return false;
	}
	
	public static void innerOutput(int i, int target, ArrayList<Integer[]> output, Stack<Integer> sb) {
		for(int j=target/2; j>=0; j--) {
			sb.add(j * j);
			
			if (isMatch(sb, target)) {
				output.add(sb.toArray(new Integer[sb.size()]));
			} else {
				if (isOk(output, sb, target)) {
					innerOutput(i + 1, target, output, sb);
				}
			}
			
			sb.pop();
		}
	}
	
	public static int findMin(ArrayList<Integer[]> output) {
		int min = Integer.MAX_VALUE;
		
		for(int i=0; i<output.size(); i++) {
			min = Math.min(min, output.get(i).length);
		}
		
		return min;
	}
	
	public static int handle(int target) {
		ArrayList<Integer[]> output = new ArrayList<>();
		
		Stack<Integer> sb = new Stack<>();
		innerOutput(0, target, output, sb);
		
		int len = findMin(output);
		
		return len;
	}
	
	public static void main(String[] args) {
		int target = 24;
		
		int output = handle(target);
		System.out.println(output);
	}
}
